package breadthFirstSearch;

import java.util.*;

public class ShortestBridge {

    /**
     * LeetCode T934 最短的桥
     * 在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
     *
     * 现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
     *
     * 返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/shortest-bridge
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param args
     */
    public static void main(String[] args) {

    }

    public int shortestBridge(int[][] grid) {
        //首先查询到某一个小岛，通过dfs获取
        int R = grid.length;
        int C = grid[0].length;
        int[][] flag = new int[R][C];
        getComponent(grid, flag);
        //bfs
        Queue<Node> queue = new LinkedList<>();
        //Set<Integer> target = new HashSet<>();
        for (int i = 0; i < R; i++){
            for (int j = 0; j < C; j++){
                if (grid[i][j] == 1 && flag[i][j] == 1){
                    queue.offer(new Node(i, j, 0));
                } /*else if (grid[i][j] == 1){
                    target.add( i * C + j);
                }*/
            }
        }
        //bfs
        while (!queue.isEmpty()){
            Node node = queue.poll();
            List<Integer> neighbors = getNeighbors(grid, node.r, node.c);
            for (Integer neighbor : neighbors) {
                int r = neighbor / C;
                int c = neighbor % C;
                if (grid[r][c] == 1 && flag[r][c] == 0){
                    return node.depth;
                }
                if (grid[r][c] == 0){
                    //标记已经遍历过
                    grid[r][c] = 1;
                    queue.offer(new Node(r, c, node.depth + 1));
                }
            }

        }
        return 0;

    }

    public void getComponent(int[][] grid, int[][] flag){
        int R = grid.length;
        int C = grid[0].length;
        Stack<Integer> stack = new Stack<>();
        //遍历得到第一个点
        for (int i = 0; i < R*C; i++){
            int r = i / C;
            int c = i % C;
            if (grid[r][c] == 1){
                flag[r][c] = 1;
                stack.push(i);
                break;
            }
        }
        while (!stack.isEmpty()){
            Integer i = stack.pop();
            int r = i / C;
            int c = i % C;
            for (Integer neighbor : getNeighbors(grid, r, c)){
                int r1 = neighbor / C;
                int c1 = neighbor % C;
                if (grid[r1][c1] == 1 && flag[r1][c1] == 0){
                    flag[r1][c1] = 1;
                    stack.push(neighbor);
                }
            }
        }
    }

    public List<Integer> getNeighbors(int[][] grid, int r, int c){
        int R = grid.length;
        int C = grid[0].length;
        List<Integer> list = new ArrayList<>();
        if (r - 1 >= 0){
            list.add(C*(r - 1) + c);
        }
        if (r + 1 < R){
            list.add((r + 1) * C + c);
        }
        if (c - 1 >= 0){
            list.add(r*C + c - 1);
        }
        if (c + 1 < C){
            list.add(r * C + c + 1);
        }
        return list;
    }


    //
}
class Node{
    public int r;
    int c;
    int depth;

    public Node(int r, int c, int depth){
        this.r = r;
        this.c = c;
        this.depth = depth;
    }
}
